package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.data.structures.unionfind.UnionFind6;
import cn.initcap.algorithm.graph.Edge;
import cn.initcap.algorithm.graph.Graph;
import cn.initcap.algorithm.graph.SparseWeightedGraph;
import cn.initcap.algorithm.sort.heap.MinHeap;
import java.util.ArrayList;
import java.util.List;

/**
 * Kruskal算法求最小生成树, 根据切分定理，每次选择权重最小的边，只要这个边不能构成环，那么这个边就是最小生成树的边
 *
 * @author initcap
 * @date Created in 1/21/19 11:10 AM.
 */
public class KruskalMst<Weight extends Number & Comparable> {

    /**
     * 最小生成树所包含的所有边
     */
    private List<Edge<Weight>> mst;
    /**
     * 最小生成树的权值
     */
    private Number mstWeight;

    /**
     * 构造函数, 使用Kruskal算法计算graph的最小生成树
     *
     * @param graph
     */
    public KruskalMst(Graph graph) {

        mst = new ArrayList<>();

        // 将图中的所有边存放到一个最小堆中
        MinHeap<Edge<Weight>> pq = new MinHeap<>(graph.marginSize());
        for (int i = 0; i < graph.nodeSize(); i++) {
            for (Object item : graph.adj(i)) {
                Edge<Weight> e = (Edge<Weight>) item;
                if (e.v() <= e.w()) {
                    pq.insert(e);
                }
            }
        }

        // 创建一个并查集, 来查看已经访问的节点的联通情况
        UnionFind6 uf = new UnionFind6(graph.nodeSize());
        while (!pq.isEmpty() && mst.size() < graph.nodeSize() - 1) {

            // 从最小堆中依次从小到大取出所有的边
            Edge<Weight> e = pq.extractMin();
            // 如果该边的两个端点是联通的, 说明加入这条边将产生环, 扔掉这条边
            if (uf.isConnected(e.v(), e.w())) {
                continue;
            }

            // 否则, 将这条边添加进最小生成树, 同时标记边的两个端点联通
            mst.add(e);
            uf.unionElements(e.v(), e.w());
        }

        // 计算最小生成树的权值
        mstWeight = mst.get(0).wt();
        for (int i = 1; i < mst.size(); i++) {
            mstWeight = mstWeight.doubleValue() + mst.get(i).wt().doubleValue();
        }
    }

    public static void main(String[] args) {

        String filename = "algorithm/testG3.txt";
        SparseWeightedGraph<Double> g = new SparseWeightedGraph<>(filename, false);

        // Test Kruskal
        System.out.println("Test Kruskal:");
        KruskalMst<Double> kruskalMst = new KruskalMst<>(g);
        List<Edge<Double>> mst = kruskalMst.mstEdges();
        for (int i = 0; i < mst.size(); i++) {
            System.out.println(mst.get(i));
        }
        System.out.println("The MST weight is: " + kruskalMst.result());

        System.out.println();
    }

    /**
     * 返回最小生成树的所有边
     *
     * @return
     */
    public List<Edge<Weight>> mstEdges() {
        return mst;
    }

    /**
     * 返回最小生成树的权值
     *
     * @return
     */
    public Number result() {
        return mstWeight;
    }

}
